iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0

選擇排序(Select Sort)

選擇排序是重複進行「將數列中最小值,與左邊的值對調」,一直保持由小到大的數列。

選擇排序法使用線性搜尋(Linear Search),比較次數是

  • 第一次:n-1
  • 第二次:n-2
  • 第n-1次:1
import random

#從1-100中隨機讀取9個數字
nums = random.sample(range(1,100), 9)
print(nums)

# nums = [60, 50, 44, 82, 55, 77]

# i控制j的上限值
for i in range(8, 0, -1):
    #初始化變數0
    max = 0
    for j in range(1, i+1):
        if nums[j] > nums[max]:
            max = j
    nums[i], nums[max] = nums[max], nums[i]
    print("選擇排序的執行結果:",9-i,"次")
    for item in nums:
        print(item,' ',end="")

輸出結果:

[35, 77, 79, 23, 18, 92, 81, 90, 12]
選擇排序的執行結果: 1 次
35  77  79  23  18  12  81  90  92  
選擇排序的執行結果: 2 次
35  77  79  23  18  12  81  90  92  
選擇排序的執行結果: 3 次
35  77  79  23  18  12  81  90  92  
選擇排序的執行結果: 4 次
35  77  12  23  18  79  81  90  92  
選擇排序的執行結果: 5 次
35  18  12  23  77  79  81  90  92  
選擇排序的執行結果: 6 次
23  18  12  35  77  79  81  90  92
選擇排序的執行結果: 7 次
12  18  23  35  77  79  81  90  92  
選擇排序的執行結果: 8 次
12  18  23  35  77  79  81  90  92

什麼是線性搜尋(Linear Search)?

線性搜尋是在陣列中搜尋數據的演算法,從陣列的前端開始依序查詢數據。也可以說,用暴力搜尋的方式在尋找數據。由於線性搜尋是從頭開始比較,當數據量大或資料在陣列的後方時,會耗費時間。當數據量為n時,執行時間是O(n^2)

def linearSearch(collection, t):
    for e in collection:
        if e == t:
            return True
    return False

上一篇
Day09:氣泡排序(Bubble Sort)
下一篇
Day11:插入排序法(Insertion Sort)
系列文
一個月的演算法挑戰30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言